1. Field of the Invention
The present invention relates to an encryption method for converting plain text to cipher (or encrypted) text, and a code -communications system using that method.
2. Description of the Related Art
In our modern society, which is called a high-level information society, important business textual and graphic information is exchanged in communications and processed as electronic information through computer network infrastructure. One characteristic of such electronic information is that it can easily be duplicated, whereupon it becomes very difficult to distinguish the duplicate from the original. Hence the problem of information security is seen to be critical. This is especially true in view of the fact that the implementation of computer networks that support features such as xe2x80x9ccomputer resource sharing,xe2x80x9d xe2x80x9cmulti-access,xe2x80x9d and xe2x80x9cwide area operationsxe2x80x9d is indispensable to the realization of the high-level information society, but these features involve aspects that are inconsistent with the protection of information exchanged between authorized participants. In this context, attention is now being drawn to coding technologies that in the past have been employed primarily in military and diplomatic communications.
Coding is exchanging of information in such a way that its meaning cannot be understood by anyone other than the authorized parties. In coding operations, the conversion of the original text (plain text) that anyone can understand to text (cipher text) the meaning of which cannot be understood by a third party is called encryption, and the restoration of that cipher text to plain text is called decryption. The overall system wherein this encryption and decryption is performed is called a cryptosystem. In the processes of encryption and decryption, respectively, secret information called encryption keys and decryption keys are employed. A secret decryption key is necessary at the time of decryption, wherefore only a party knowledgeable of that decryption key can decrypt the cipher text. The confidentiality of the information is accordingly maintained by the encryption.
Cryptosystems can be subsumed under two broad categories, namely common key cryptosystems and public key cryptosystems. In a common key cryptosystem, the encryption key and the decryption key are identical, and coded communications are conducted by having both the sending party and receiving party hold the same key. The sending party encrypts plain text based on the common secret key and send it to the receiving party, whereupon the receiving party uses the same key to decrypt the cipher text and restore it to the original plain text.
In contrast thereto, in a public key cryptosystem, the encryption key and decryption key are different. In conducting coded communications in this cryptosystem, the sending party encrypts the plain text with the public key derived from a receiving party, and the receiving party decrypts that cipher text with his or her own secret key. The public key is used for encryption, and the secret key is a key for decrypting the cipher text converted by the public key. The cipher text converted by the public key can only be decrypted using a secret key.
One example of such a public key cryptosystem is seen in the conventional knapsack coding schemes wherein safety is based on the knapsack problem. However, almost all of the knapsack coding schemes now being proposed exhibit either linearity or super-increasing, wherefore it has been demonstrated that they can be decrypted using the Shamir attack method and Lenstra-Lenstra-Lovasz (LLL) algorithms. To overcome this shortcoming, multiplication knapsack coding schemes have been developed which employ power operation over modulo-calculation, an example whereof is seen in the Morii-Kasahara cryptosystem (Masakatsu Morii and Masao Kasahara: xe2x80x9cDenshi Joho Tsushin Gakkai [Electronic Information Communications Society],xe2x80x9d Vol. j71-D, No. 2 (1988)). This Morii-Kasahara cryptosystem (hereinafter referred to as the MK cryptosystem) is now described.
In this description, the following three definitions are given.
(Divisibility Discriminator Symbol)
A divisibility discriminator symbol  less than   greater than  for determining whether or not b is evenly divisible by a is defined below.       ⟨          b      a        ⟩    ⁢      =    def    ⁢      {                            0                                      (                          when              ⁢                              xe2x80x83                            ⁢              b              ⁢                                                xe2x80x83                                ⁢                                  xe2x80x83                                            ⁢              is              ⁢                              xe2x80x83                            ⁢              not              ⁢                              xe2x80x83                            ⁢              evenly              ⁢                              xe2x80x83                            ⁢              divisible              ⁢                              xe2x80x83                            ⁢              by              ⁢                              xe2x80x83                            ⁢              a                        )                                                1                                      (                          when              ⁢                              xe2x80x83                            ⁢              b              ⁢                              xe2x80x83                            ⁢              is              ⁢                              xe2x80x83                            ⁢              evenly              ⁢                              xe2x80x83                            ⁢              divisible              ⁢                              xe2x80x83                            ⁢              by              ⁢                              xe2x80x83                            ⁢              a                        )                              xe2x80x83(Scalar exponentiation) C=Ae
If A and C are vectors and e is a scalar, then scalar exponentiation is defined as follows.
(Scalar exponentiation) C=Ae
cij=aeij
(Matrix right exponentiation) C=AB
If A, B, and C are vectors, then right exponentiation of matrix is defined as follows.                                           (                          matrix              ⁢                              xe2x80x83                            ⁢              right              ⁢                              xe2x80x83                            ⁢              exponentiation                        )                    ⁢                      xe2x80x83                    ⁢          C                =                  A          B                                                  c          ij                =                              ∏            k                    ⁢                      xe2x80x83                    ⁢                      a            ik                          b              kj                                          
(Key Generation)
In the MK cryptosystem, the secret and public keys are generated as follows.
Condition 1:                              p          MK                 greater than                               ∏                          i              =              1                        n                    ⁢                      xe2x80x83                    ⁢                      a            i                                              (        1        )            
(Encryption)
Treating the plain text as the vector x=t(x1, x2, . . . , xn), the sending party creates the cipher text C by the following equation and sends it to the receiving party.                     C        =                              c                        x                                        t                    =                                    ∏                              i                =                1                            n                        ⁢                          xe2x80x83                        ⁢                                          c                i                xi                            ⁢                              xe2x80x83                            ⁢                              (                                  mod                  ⁢                                      xe2x80x83                                    ⁢                                      p                    MK                                                  )                                                                        xe2x80x83            
(Decryption)
The receiving party, using the following equation, raises the received cipher text C to the power of d and converts it to A.
A=Cd=(tcx)d=taedx=tax(mod pMK)
Then, as represented in the following equation, divisibility determination is performed on A using the components of the secret vector a, whereby decryption can be done to obtain the original plain text vector.   x  =                   t        ⁢          (                        ⟨                      A                          a              1                                ⟩                ,                  xe2x80x83                ⁢                  ⟨                      A                          a              2                                ⟩                ,        …        ⁢                  xe2x80x83                ,                  ⟨                      A                          a              n                                ⟩                    )      
Specific examples involving this MK cryptosystem are described next.
(Key Generation)
Secret key
vector a=t(13, 9, 25, 16, 7, 17)
e=1501, d=11131
Public key
pMK=5569211 to satisfy Condition 2 below                               vector          ⁢                      xe2x80x83                    ⁢          c                =                  xe2x80x83                ⁢                  vector          ⁢                      xe2x80x83                    ⁢                      a            ⅇ                                                  =                  xe2x80x83                ⁢                                           t                    ⁢                      (                                          13                1501                            ,                              9                1501                            ,                              25                1501                            ,                              16                1501                            ,                              7                1501                            ,                              17                1501                                      )                                                  =                  xe2x80x83                ⁢                                           t                    ⁢                      (                          5097951              ,              4832634              ,              2171018              ,              2905496              ,                                                                                    xe2x80x83                    ⁢                      1517072            ,            319194                    )                ⁢                  xe2x80x83                ⁢                  (                      mod            ⁢                          xe2x80x83                        ⁢            5569211                    )                    
Condition 2:
pMK=5569211 greater than Πi=16ai=5569200xe2x80x83xe2x80x83(2)
(Encryption)
Encryption is performed, treating the plain text as the vector                     x        =                                                           t                        ⁢                          (                              1                ,                0                ,                1                ,                1                ,                1                ,                0                            )                                .                                        C        =                  5097951          ·          2171018          ·          2905496          ·          1517072                                        =                  5328558          ⁢                      xe2x80x83                    ⁢                      (                          mod              ⁢                              xe2x80x83                            ⁢              5569211                        )                              
(Decryption)
After raising the cipher text C to the power of d to obtain A, the original plain text vector x is obtained by performing divisibility determination on A using the components of the secret vector a, as in Equation 3 below.
A=Cd=532855811131=36400(mod 5569211)
                                                        x              =                                                                   t                                ⁢                                  (                                                            ⟨                                              36400                        13                                            ⟩                                        ,                                          ⟨                                              36400                        9                                            ⟩                                        ,                                          ⟨                                              36400                        25                                            ⟩                                        ,                                          ⟨                                              36400                        16                                            ⟩                                        ,                                                                  ⟨                                                  36400                          7                                                ⟩                                            ⁢                                              ⟨                                                  36400                          17                                                ⟩                                                                              )                                                                                                        =                                                                   t                                ⁢                                  (                                      1                    ,                    0                    ,                    1                    ,                    1                    ,                    1                    ,                    0                                    )                                                                                        (        3        )            
The MK cryptosystem described in the foregoing is thought to provide a high degree of safety, but has problems, namely that the cipher text rate is low relative to the plain text rate, and that encryption efficiency is poor. If we here represent the size of the plain text and cipher text as n bits and k bits, respectively, we can define the encryption efficiency as the rate xcex7 by the Equation 4 below.
xcex7=n/kxe2x80x83xe2x80x83(4)
In MK encryption, the plain text is divided into n-bit block units, so the size of the plain text becomes a constant (n bits). The size of the cipher text, on the other hand, is determined solely by the size of the modulus pMK. Accordingly, the following Equation 5 is established for the rate xcex7MK in the MK encryption.                               η          MK                =                                            n                                                log                  2                                ⁢                                  p                  MK                                                       less than                           n                                                log                  2                                ⁢                                                      ∏                                          i                      =                      1                                        n                                    ⁢                                      xe2x80x83                                    ⁢                                      a                    i                                                                                =                      n                                          ∑                                  i                  =                  1                                n                            ⁢                                                log                  2                                ⁢                                  a                  i                                                                                        (        5        )            
Thus, in the MK cryptosystem, it is necessary to make the modulus a prime number that is larger than the product of all ai (see Equation 1), wherefore the value of the rate xcex7MK is not always high. Even if the average size of ai is made 10 bits, for example, in Equation 5, the upper limit of the rate xcex7MK will be no more than 0.1 or so. And even if prime numbers are used in order beginning from the smallest, as in vector a=t(2, 3, 5, 7, . . . ), the rate xcex7MK will be around 0.156 when n=60. There is also a problem of the value of the modulus being too high, resulting in low practicality.
The present invention was devised in view of the circumstances described in the foregoing.
An object of the present invention is to provide an encryption method which can greatly improve the rate in comparison with conventional MK cryptosystems, together with a code communications system using that method.
Another object of the present invention is to provide a practical encryption method which is executable with a modulus of small value.
The encryption method according to one aspect of the present invention is an encryption method for converting binary sequence plain text into cipher text, wherein the plain text is converted into binary sequence expanded plain text having a larger number of bits than the original plain text, and that expanded plain text is encrypted into cipher text.
The conversion of the plain text into the expanded plain text may be performed so as to limit the weight of the plain text. If the number of bits in the plain text and the expanded plain text is expressed by n and m (where n less than m) respectively and the weight of the plain text is limited to w, m may be determined so as to satisfy the relationship mCwxe2x89xa72n. When converting the plain text to the expanded plain text, a Schalkwijk decoding algorithm may be used.
When the number of bits of the plain text and the expanded plain text is n and m (where n less than m) respectively and the weight of the plain text is limited to w or lower, m may be determined satisfy Condition A shown below.
Condition A:                                           ∑                          k              =              0                        w                    ⁢                      C            k                                      m                                        ≥                  2          n                                    (        A        )            
When converting the plain text to the expanded plain text, an extended Schalkwijk decoding algorithm may be used.
According to another aspect of the present invention, there is provided an encryption method for converting a binary sequence of n bits of plain text to cipher text comprising the steps of: finding m (where n less than m) which satisfies the condition mCwxe2x89xa72n, in order to limit the weight of the n bits of plain text to w; converting the n bits of plain text to a binary sequence of m bits of expanded plain text by a Schalkwijk decoding algorithm while assuming that the n bits of plain text be an integer and this integer be an index; and producing cipher text using the expanded plain text and a public key.
According to the third aspect of the present invention, there is provided an encryption method for converting a binary sequence of n bits of plain text to cipher text comprising the steps of: finding m (where n less than m), which satisfies Condition A noted below, in order to limit the weight of the n bits of plain text to w; converting the n bits of plain text to a binary sequence of m bits of expanded plain text by an extended Schalkwijk decoding algorithm while considering that the n bits of plain text be an integer and this integer be an index; and producing cipher text using the expanded plain text and a public key.
Condition A:                                           ∑                          k              =              0                        w                    ⁢                      C            k                                      m                                        ≥                  2          n                                    (        A        )            
According to the fourth aspect of the present invention, there is provided an encryption/decryption apparatus which comprises: an encryptor for producing cipher text from plain text using one of the encryption methods described above; and a decrypter for decrypting the cipher text so produced back into the original plain text.
According to the fifth aspect of the present invention, there is provided a code communications system for communicating information based on cipher text between a plurality of entities, comprising: an encryptor for producing cipher text from plain text using one of the encryption methods described above; a communication path for transmitting the cipher text from one entity to another entity; and a decrypter for decrypting the cipher text so transmitted back into the original plain text.
The concept underlying the encryption method of the present invention is now described.
FIG. 1A of the accompanying drawings illustrates the concept underlying a conventional MK cryptosystem and FIG. 1B illustrates the encryption method of the present invention.
In the conventional MK cryptosystem, the number of bits having weight (the number of 1s) cannot be limited, wherefore the prime number pMK that becomes the modulus must be determined in consideration of the product of all of the secret vector components so that decryption can uniquely be done even when all of the components of the plain text are 1s. Accordingly, that prime number pMK always ends up being a large number. As a result, as diagramed in FIG. 1A, the number of bits in the cipher text becomes large, so that only a low rate can be obtained.
If the plain text is converted to a binary sequence with a limited weight prior to the encrypting conversion, and that binary sequence is treated as plain text and subjected to MK encryption, unique decryption can be guaranteed without using the large modulus. The present invention takes advantage of this principle. Specifically, the binary sequence plain text is first converted to binary sequence plain text having limited weight (expanded plain text), and then that expanded plain text is encrypted. This two-step (conversion-encrypting) process is diagramed in FIG. 1B. Conversion to the expanded plain text is done first, wherefore the bit count increases to a certain extent at that point, but the weight has been limited so that in the subsequent encryption a smaller modulus can be used than in the conventional MK cryptosystem. As a result, the number of bits in the cipher text can be made smaller than conventionally. Consequently, the rate can be sharply improved.
As a procedure for converting plain text to expanded plain text of limited weight, either a Schalkwijk algorithm or an extended Schalkwijk algorithm (which will be defined below) obtained by extending that Schalkwijk algorithm can be used. Hereinafter, the encryption method of the present invention which uses a Schalkwijk algorithm is called the first invention, and the encryption method of the present invention which uses an extended Schalkwijk algorithm is called the second invention. These are now described in more specific terms.
A brief description is first given here of the Schalkwijk algorithm. Let us consider a set S(m,w) of binary vectors containing size bits m and constant weight value bits w. The Schalkwijk algorithm is a known procedure for making a definitive (or one-to-one) association between any vector s belonging to S(m,w) and an index i from 0 to mCwxe2x88x921. When a Schalkwijk encoding algorithm is employed, the index i corresponding to an arbitrary vector sxcex5S(m,w) can be found. Conversely, when a Schalkwijk decoding algorithm is employed, the vector sxcex5S(m,w) corresponding to a given index i can be found. (Schalkwijk encoding algorithm)
To find an index i from a sequence vector s having a size of m bits and a weight of w bits (s=(s1, . . . , sm)xcex5S(m,w)):
(Schalkwijk Decoding Algorithm)
To find a size m bit and weight w bit sequence vector s=(s1, . . . , sm)xcex5S(m,w) from an index i:
The encryption and decryption procedures in the first invention are now described. In the first invention, using the Schalkwijk algorithms described in the foregoing, the original plain text is converted to expanded plain text wherein the weight value is limited to w, and that expanded plain text is encrypted as in the conventional MK cryptosystem. In FIG. 2 of the accompanying drawings is given a flowchart for the encryption processing procedure, while in FIG. 3 is given a flowchart for the corresponding decryption processing procedure. When the sizes of the expanded and original plain texts are m bits and n bits, respectively, the difference (mxe2x88x92n) is defined as the expanded bit count.
 less than  less than Encryption greater than  greater than 
(Expanded Plain Text Conversion)
In order to limit the plain text weight to w, the size m of the expanded plain text which satisfies Condition 6 below is found (step S1). Treating an n-bit plain text vector x as an integer, and taking this integer as the index i, we use the Schalkwijk decoding algorithm to convert the plain text vector x to the expanded plain text vector sxcex5S(m,w) (step S2).
Condition 6:
mCwxe2x89xa72nxe2x80x83xe2x80x83(6)
(Encrypting Conversion)
A prime number pA which satisfies Condition 7 below is found (step S3).
Condition 7:                               p          A                 greater than                               Max                          s              ⁢                              xe2x80x83                            ⁢              ε              ⁢                              xe2x80x83                            ⁢                              S                ⁡                                  (                                      m                    ,                    w                                    )                                                              ⁡                      (                          a                                            s                ⁢                                  xe2x80x83                                                                            t                        )                                              (        7        )            
The symbol Max ( ) indicates the maximum value in the parentheses ( ), and the vector a is a secret vector comprised of m components.
The receiving party determines e and finds d using pAxe2x88x921 as the modulus. A public vector c is generated as in the conventional MK cryptosystem. The sending party generates cipher text C, as follows, using the public vector c and the expanded plain text vector s of the receiving party (step S4).
C=tcs(mod pA)
 less than  less than Decryption greater than  greater than 
(Decrypting Conversion)
The cipher text C is decrypted as in the conventional MK cryptosystem, and the expanded plain text vector s belonging to S(m,w) is found (step S11).
(Plain Text Conversion)
The expanded plain text vector s is decrypted using the Schalkwijk decoding algorithm and thereby converted to the index i (step S12). This is treated as an n-bit binary number and the original plain text vector x is obtained (step S13).
A brief description is first given of the extended Schalkwijk algorithm as defined by the inventors with reference to Schalkwijk. A set T(m,w) of binary vectors having a size of m bits and a weight of w bits at most is posited. Specifically, the following conditions are satisfied.       T    ⁡          (              m        ,        w            )        =            ⋃              0        ≦        j        ≦        w              ⁢          S      ⁡              (                  m          ,          j                )            
Here, the extended Schalkwijk algorithm is defined as an operation for definitively associating any vector s belonging to T(m,w) with an index i given by Equation 8 below.                     0        ∼                                            ∑                              g                =                0                            w                        ⁢                          C              g                                            m                                                -          1                                    (        8        )            
Using the extended Schalkwijk encoding algorithm, we can find the index i associated with an arbitrary vector sxcex5T(m,w). Conversely, using the extended Schalkwijk decoding algorithm, we can find the vector sxcex5T(m,w) corresponding to a given index i.
(Extended Schalkwijk Encoding Algorithm)
To find the index i from a sequence vector s=(s1, . . . , sm)xcex5T(m,w) having a size of m bits and a weight of w bits or less (where w(s) is the weight of the vector s):       Extended    ⁢          xe2x80x83        ⁢    Schalkwijk    ⁢          xe2x80x83        ⁢          Encode      ⁡              (        s        )                        xe2x80x83        ⁢          {              
            ⁢              xe2x80x83            ⁢                        i          ⇐                                    SchalkwijkEncode              ⁡                              (                s                )                                      +                                          ∑                                  g                  =                  0                                                                      w                    ⁡                                          (                      S                      )                                                        -                  1                                            ⁢                              xe2x80x83                            ⁢                              C                g                                                  m                                                                      ;                  
                ⁢                  xe2x80x83                ⁢                  return          ⁡                      (            i            )                          ;            ⁢              
            ⁢              xe2x80x83            }      
(Extended Schalkwijk Decoding Algorithm)
To find the sequence vector s=(s1, . . . , sm)xcex5T(m,w) having a size of m bits and weight of w bits or less, from the index i:       Extended    ⁢          xe2x80x83        ⁢    Schalkwijk    ⁢          xe2x80x83        ⁢          Decode      ⁡              (                  i          ,          m                )                        xe2x80x83        ⁢          {              
            ⁢              xe2x80x83            ⁢                                    w            xe2x80x2                    ⇐          0                ;                  
                ⁢                  xe2x80x83                ⁢                              while            ⁢                          xe2x80x83                        ⁢                          (                                                i                  -                                                            ∑                                              g                        =                        0                                                                    w                        xe2x80x2                                                              ⁢                                          xe2x80x83                                        ⁢                                          C                      g                                                                    m                                                                                              ≥                0                            )                        ⁢                          {                                                                    w                    xe2x80x2                                    ⇐                                                            w                      xe2x80x2                                        +                    1                                                  ;                            }                        ⁢                          
                        ⁢                          xe2x80x83                        ⁢            w                    ⇐                                    w              xe2x80x2                        -            1                          ;                  
                ⁢                  xe2x80x83                ⁢                              i            xe2x80x2                    ⇐                      i            -                                          ∑                                  g                  =                  0                                w                            ⁢                                                C                  g                                                        m                                                    ⁢                                  
                                ⁢                                  xe2x80x83                                ⁢                s                                              ⇐                                    SchalkwjkDecode              ⁡                              (                                                      i                    xe2x80x2                                    ,                  m                  ,                  w                                )                                      ⁢                          
                        ⁢                          xe2x80x83                        ⁢                          return              ⁡                              (                s                )                                                    ;            ⁢              
            ⁢              xe2x80x83            }      
The procedures for encryption and decryption in the second invention are described next. In the first invention, the rate is improved by converting the plain text to expanded plain text having its weight limited to the constant value w, prior to encryption conversion, using a Schalkwijk algorithm. In the second invention, the extended Schalkwijk algorithm described earlier is used to allow the weight of the expanded plain text to have a value equal to or lower than w, and thereby improving the rate even further than in the first invention. FIG. 4 of the accompanying drawings depicts a flowchart for the encryption procedure according to the second invention and FIG. 5 depicts a flowchart for the decryption procedure.
 less than  less than Encryption greater than  greater than 
(Expanded Plain Text Conversion)
In order to limit the plain text weight to w or lower, the size m of expanded plain text that satisfies Condition 9 below is sought (step S21).
Condition 9:                                           ∑                          k              =              0                        w                    ⁢                      C            k                                      m                                        ≥                  2          n                                    (        9        )            
Treating an n-bit plain text vector x as an integer and taking this integer as the index i, we use the extended Schalkwijk decoding algorithm to convert the plain text vector x to the expanded plain text vector sxcex5T(m,w) (step S22).
(Encrypting Conversion)
A prime number pB which satisfies Condition 10 below is found (step S23).
Condition 10:                               p          B                 greater than                               Max                          s              ⁢                              xe2x80x83                            ⁢              ε              ⁢                              xe2x80x83                            ⁢                              T                ⁡                                  (                                      m                    ,                    w                                    )                                                              ⁡                      (                          a                                            s                ⁢                                  xe2x80x83                                                                            t                        )                                              (        10        )            
The receiving party determines e and finds d using pBxe2x88x921 as the modulus. A public vector c is generated as in the conventional MK cryptosystem. The sending party generates cipher text C, as follows, using the public vector c and the expanded plain text vector s of the receiving party (step S24).
C=tcs(mod pB)
 less than  less than Decryption greater than  greater than 
(Decrypting Conversion)
The cipher text C is decrypted as in the conventional MK cryptosystem, and the expanded plain text vector s belonging to T(m,w) is found (step S31).
(Plain Text Conversion)
The expanded plain text vector s is decrypted using the extended Schalkwijk decoding algorithm and thereby converted to the index i (step S32). This is treated as an n-bit binary number and the original plain text vector x is obtained (step S33).